A. Cochlear Implants
Modern cochlear implant prostheses provide a wide variety of fitting options that can be customized for each individual recipient. At the highest level, one of several stimulation ‘strategies’ may be selected. Each strategy defines an algorithm for converting acoustic sound input into a sequence of electrical stimuli applied to electrodes within the cochlea. Examples of strategies currently in clinical use are the SPEAK, ACE, CIS and SAS strategies.
Within any given strategy a great many parameters and parameter values may be set to tailor the encoding and stimulation for an individual patient. Examples of parameters and parameter values that may be selected for a strategy are the number of frequency bands (channels) represented, the intracochlear and/or extracochlear electrodes associated with each channel, the pulse repetition rate for each channel, the pulse width for each channel, the number of spectral maxima periodically chosen for representation, the mapping of sound pressure to stimulus current for each channel (thresholds, comfort levels and compression curves), front end filtering of the audio from the microphone (pre-emphasis), and automatic gain control threshold, compression ratio, and attack and release times. (As used herein, the term ‘parameter values’ refers collectively to values of parameters, whether selectable options are programmed on or off, and in general to any choices that are made during a fitting procedure.)
The ability of a cochlear implant user to understand speech or recognize other sounds depends strongly on the strategy selection and the adjustment of parameters. It is known that no single set of parameters provides an optimal outcome for all users. Users are heterogeneous such that, in general, each user requires a different set of parameters to achieve optimal performance. Parameter values must be tailored to the individual in order to maximize speech reception or user satisfaction.
The task of the clinical professional, usually an audiologist, is to choose a et of parameters—called a ‘MAP’—that will provide the best possible outcome for an individual user. Because there are hundreds or thousands of possible MAPs, it is not practical to try all of the alternatives exhaustively and to evaluate performance of each for an individual user. Nor is it possible to identify an optimal MAP by prescription based upon a limited set of measures as is, for example, the case in fitting eyeglasses or a hearing aid. Optimal fitting of cochlear implants by prescriptive testing has not proved to be consistently successful. Nor is it possible to optimize parameters one at a time, adjusting each in succession to its best value. This is because the parameters interact strongly, and often non-monotonically. For example, increasing stimulus rate may improve the outcome for one set of electrodes, but worsen it for another set.
As a result, clinicians have adopted a variety of approaches for fitting the device parameters to the patient. Some simply fit default parameters to all users. Some adopt preferred MAPs, which they believe are good, if not best, for many or most individuals. These may be based upon personal experience, published performance data, or intuition. Some clinicians evaluate a limited set of alternatives. Some attempt to adjust individual parameters based upon measured perceptual limitations and inferred relationships to fitting parameters. These approaches are time consuming, costly, and unreliable.
The fundamental problem remains that there is no known method for systematically identifying the particular MAP that achieves the best outcome for an individual patient. And this problem is exacerbated each time that manufacturers expand available parameter ranges or introduce new encoding strategies.
In the absence of a prescriptive procedure, an adaptive procedure can sometimes be employed to solve an optimization problem. An adaptive procedure steps through a sequence of solutions with the objective of converging gradually towards the best one. Traditional analytic optimization procedures use current and past measurements of performance to predict, at each iteration, parameter adjustments that will incrementally improve the outcome. But these methods generally fail when there are strong nonlinear and nonmonotonic interactions among parameters as is the case in cochlear implant fitting. They may converge toward a local maximum rather than the absolute maximum, or fail to converge at all. They may also fail when the measurements are noisy, as is often the case when measuring auditory response in humans.
The problem referred to can be appreciated by studying FIGS. 1A and 1B. They represent a simple case in which values for only two parameters, on the X and Y axes, must be determined. The vertical (Z) axis represents the ‘fitness function,’ i.e. how good a result is produced by each X-Y pair of values. In FIG. 1A, the value of either variable can be optimized without radically affecting optimization of the other. There is only one ‘hump’ and eventually an adaptive procedure will give rise to X and Y values whose fitness function is a maximum, at the top of the hump. But in FIG. 1B, changing the value of either variable affects the optimum value of the other. Once the variable values are situated on a hump, the adaptive procedure may give rise to X and Y values whose fitness function is a local maximum (at the top of the hump), but there may be another hump, with a higher peak, that the variables never even reach. It has been believed that adaptive procedures in fitting a cochlear implant would converge toward a local maximum rather than a global maximum, and that adaptive procedures might not converge at all.
B. The Genetic Algorithm
The genetic algorithm is an adaptive procedure, based on a simple model of biological evolution, which can be used to find optimal solutions to a problem. The procedure implements ‘natural selection’ (survival of the fittest), ‘procreation with inheritance,’ and random ‘mutation.’ Genetic algorithms generally resist convergence on local maxima. The underlying premise is that the evolutionary process will, over multiple generations, produce an ‘organism’ which is optimal in the sense that it is most likely to survive and procreate.
Each iteration of the genetic algorithm procedure begins with one generation of organisms and produces a succeeding generation. This involves two steps: (1) selection—choosing a subset of organisms as potential ‘parents’ of the organisms (‘children’) of the succeeding generation; and (2) procreation—creation of ‘children’ from sets of potential ‘parents’ (usually pairs).
In genetic algorithms, selection operates on strings of binary digits stored in the computer's memory, and over time, the functionality of these strings evolves in much the same way that natural populations evolve. Genetic algorithms are capable of evolving surprisingly complex and interesting structures. These structures may represent not only solutions to problems, but also strategies for playing games, visual images, or even simple computer programs. The Darwinian theory of evolution depicts biological systems as the product of the ongoing process of natural selection. Likewise, genetic algorithms allow engineers to use a computer to evolve solutions over time, instead of designing them by hand. Because almost any method, theory, or technique can be programmed on a computer, this implies an approach to problem solving that can be, at least partially, automated by a computer.
The basic idea of a genetic algorithm is that first a population of organisms is created in a computer (typically with genes stored as binary strings in the computer's memory), and then the population is evolved with use of the principles of variation, selection, and inheritance. There are many ways of implementing this idea, but the most basic is that suggested by J. H. Holland, in Adaptation in Natural and Artificial Systems, Univ. of Michigan Press, Ann Arbor, Mich., 1975, reprinted by MIT Press, Cambridge, Mass., 1992. Each of a group of organisms in a ‘generation’ is assigned a fitness value by a fitness function. On the basis of these fitness values, the selection phase ranks the organisms. After selection, genetic operators are applied probabilistically; some organisms may have bits in their genes mutated from a 1 to a 0 or a 0 to a 1, and parts of different organisms' genes are then combined into new ones. The resulting population comprises the next generation and the process repeats itself.
The fitness function is the primary place in which the traditional genetic algorithm is tailored to a specific problem. Once all organisms in the population of a particular generation have been evaluated, their fitnesses are used as the basis for selection. Selection is implemented by eliminating low-fitness individuals from the population, and inheritance is often implemented by making multiple copies of high-fitness individuals. Genetic operators such as mutation (flipping individual bits) and crossover or inheritance (exchanging sub-strings of two organisms to obtain two offspring) are applied probabilistically to the selected individuals to produce new organisms. By replacing members of the old generation with such new organisms, new generations are produced either synchronously, so that the old generation is completely replaced, or asynchronously, so that the new and old members of the generation overlap. The genetic operators have been shown to generate new organisms that, on average, are better than the average fitness of their parents. Therefore, when this cycle of evaluation, selection, and genetic operations is iterated for many generations, the overall fitness of the population generally improves, on average, and the organisms in the population represent improved ‘solutions’ to whatever problem was posed in the fitness function.
Selection can be performed in any of several ways. It can arbitrarily eliminate the least fit 50% of the population and make one copy of all the remaining organisms, it can replicate organisms in direct proportion to their fitness, or it can scale the fitnesses in any of several ways and replicate organisms in direct proportion to their scaled values (a more typical method). Likewise, the crossover operator can pass on both offspring to the new generation, or it can arbitrarily choose one to be passed on. These and other variations of the basic algorithm are well known in the art.
C. The Genetic Algorithm and Cochlear Implants
The genetic algorithm has been applied to hearing aids, the art closest to that of cochlear implants. The fitness function in this type of case is not based on application of a formula. Rather, the user provides feedback in the form of accepting or rejecting organisms in a population, where each organism is a set of parameter values, or the user ranks the organisms and thus affects which organisms populate the next generation. This variation of the genetic algorithm, involving feedback or interactivity, is discussed in a review article by H. Takagi, Interactive Evolutionary Computation: Fusion of the Capabilities of EC Optimization and Human Evaluation, Proceedings of the IEEE, Vol. 89, No. 9, September 2002., pp. 1275-1296.
The genetic algorithm has not been applied, however, to cochlear implants. Even though there is an extensive literature on the genetic algorithm, including applications with a human observer in the loop and one specifically fitting hearing aids, the task of fitting a cochlear implant is so daunting that most workers did not believe the genetic algorithm could be adapted to cochlear implants. The hearing aid prior art obliged the listener to scale (assign a numerical value to) each member of the population. Even experienced cochlear implant users cannot reliably scale the quality of the percept. The sound sensation varies so much across fittings, and can be disparate in so many ways, that numerical scaling is essentially impossible. So all prior art using scaling in the evaluation function is impractical for the cochlear implant task. This is even more of a problem with naive (newly implanted) users, to whom all of the percepts are foreign. Even ranking without scaling would be difficult for new users.
Moreover, the complexity of the fitting (the number of parameters to be adjusted) would demand too many bits in each population member. With many bits, the number of members per population must be high, and that would swamp the user with choices to evaluate. This is both impractical in time spent, and impossible for the listener who cannot reasonably compare many simultaneous options.